#include <iostream>
#include <string_view>
#include <array>

using std::cout;
using std::endl;
using std::array;
using std::string_view;

// 求两个序列的公共子序列的最大长度

/*
l = "helloworld";
r = "hloweold";

l: l0, l1... ln
r: r0, r1... rm

if l[n] == r[m]:
    LCS(l, r) = LCS(l[n-1], r[m-1]) + 1
else:
    LCS(l, r) = max{ LCS(l[n-1], r[m]) LCS(l[n], r[m-1]) }

*/
int fun1(string_view lhs, string_view rhs, int lLen, int rLen)
{
    if(lLen == -1 || rLen == -1){
        return 0;
    }

    if(lhs[lLen] == rhs[rLen]){
        return fun1(lhs, rhs, lLen - 1, rLen - 1) + 1;
    }else{
        return std::max(fun1(lhs, rhs, lLen - 1, rLen), fun1(lhs, rhs, lLen, rLen - 1));
    }

}

int **dp = nullptr;
int **path = nullptr;
int cnt = 0;

int fun2(string_view lhs, string_view rhs, int lIdx, int rIdx)
{

    if(lIdx < 0 || rIdx < 0){
        return 0;
    }
    if(dp[lIdx][rIdx] != -1){
        cnt++; 
        return dp[lIdx][rIdx];
    }

    if(lhs[lIdx] == rhs[rIdx]){
        dp[lIdx][rIdx] = fun2(lhs, rhs, lIdx - 1, rIdx - 1) + 1;
        path[lIdx][rIdx] = 1;
    }else{
        int val1 = fun2(lhs, rhs, lIdx, rIdx - 1);
        int val2 = fun2(lhs, rhs, lIdx - 1, rIdx);
        if(val1 >= val2){
            dp[lIdx][rIdx] = val1;
            path[lIdx][rIdx] = 2; // lIdx, rIdx - 1
        }else{
            dp[lIdx][rIdx] = val2;
            path[lIdx][rIdx] = 3;// lIdx - 1, rIdx

        }
    }
    return dp[lIdx][rIdx];
}

void getRetStr(string_view sv1, int lIdx, int rIdx)
{
    if(lIdx < 0 || rIdx < 0) return;
    if(path[lIdx][rIdx] == 1){
        getRetStr(sv1, lIdx - 1, rIdx - 1);
        cout << sv1[lIdx];
    }else if(path[lIdx][rIdx] == 2){
        getRetStr(sv1, lIdx, rIdx - 1);
    }else{
        getRetStr(sv1, lIdx - 1, rIdx);
    }
}

void getRetStr2(string_view sv1, string_view sv2)
{
    int sv1Idx = sv1.size() - 1, sv2Idx = sv2.size() - 1;
    std::string ret;
    ret.resize(dp[sv1Idx][sv2Idx]);
    int i = dp[sv1Idx][sv2Idx] - 1;

    for(;sv1Idx >= 0 && sv2Idx >= 0;){
        if(path[sv1Idx][sv2Idx] == 1){
            ret[i--] = sv1[sv1Idx];
            sv1Idx -= 1;
            sv2Idx -= 1;
        }else if(path[sv1Idx][sv2Idx] == 2){
            sv2Idx -= 1;
        }else{
            sv1Idx -= 1;
        }
    }
    cout << ret << endl;
    
}

int getMax(int i, int j)
{
    int max = 0;
    for(;i >= 0;){
        for(;j >= 0;){
            if(dp[i][j] > max) max = dp[i][j];
        }
    }
    return max;
}

int fun3(string_view sv1, string_view sv2)
{
    for(int i{1}; i <= sv1.size(); i++){
        for(int j{1}; j <= sv2.size(); j++){
            if(sv1[i] == sv2[j]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[sv1.size()][sv2.size()];
}

int main(int args, char *argv[])
{
    string_view sv1 = "helloworlddf";
    string_view sv2= "hlowreoldasd";

    // cout << sizeof(sv1) << endl;
    dp = new int*[sv1.size() + 1];
    for(int i{}; i <= sv1.size(); i++){
        dp[i] = new int[sv2.size() + 1];
        for(int j{};j <= sv2.size(); j++){
            dp[i][j] = 0;
        }
    }

    // path = new int*[sv1.size()];
    // for(int i{}; i < sv1.size(); i++){
    //     path[i] = new int[sv2.size()];
    //     for(int j{};j < sv2.size(); j++){
    //         path[i][j] = -1;
    //     }
    // }

    cout << fun3(sv1, sv2) << endl;
    // cout << fun1(sv1, sv2, sv1.size() - 1, sv2.size() - 1) << endl;
    // cout << fun2(sv1, sv2, sv1.size() - 1, sv2.size() - 1) << endl;
    // cout << "比不使用动态规划少计算了" << cnt << "次" << endl;

    /* for(int i{}; i < sv1.size();++i ){
        for(int k{}; k < sv2.size(); ++k){
            if(path[i][k] == -1)
                cout << "*" << " ";
            else    
                cout << path[i][k] << " ";
        }
        cout << endl;
    } */

    // getRetStr(sv1, sv1.size() - 1, sv2.size() - 1);
    cout << endl;
    // getRetStr2(sv1, sv2);

    // 释放dp内存
    for(int i{}; i < sv1.size(); i++){
        delete [] dp[i];
    }

    // for(int i{}; i < sv1.size(); i++){
        // delete [] path[i];
    // }
    return 0;
}